/**
 * 10. 正则表达式匹配
 * https://leetcode-cn.com/problems/regular-expression-matching/
 */
public class Solutions_10 {
    public static void main(String[] args) {
//        String s = "aa", p = "a";  // output: false
//        String s = "aa", p = "a*";  // output: true
//        String s = "ab", p = ".*";  // output: true
//        String s = "aab", p = "c*a*b";  // output: true
//        String s = "mississippi", p = "mis*is*p*.";  // output: false
        String s = "aaa", p = "a*";  // output: true
//        String s = "aa", p = "*a";  // output: false

        boolean result = isMatch(s, p);
        System.out.println(result);
    }

    /**
     * 关键："" 与 "a*" 也是匹配的，所以 i 要从 0 开始遍历
     */
    public static boolean isMatch(String s, String p) {
        char[] sarr = s.toCharArray();
        char[] parr = p.toCharArray();
        int slen = sarr.length, plen = parr.length;
        // dp[3][5] = true，表示字符串 s 前 3 个字符与字符串 p 前 5 个字符能够匹配
        // dp[3][5] = false，表示字符串 s 前 3 个字符与字符串 p 前 5 个字符不能够匹配
        boolean[][] dp = new boolean[slen + 1][plen + 1];
        dp[0][0] = true;

        for (int i = 0; i <= slen; i++) {
            for (int j = 1; j <= plen; j++) {
                if (parr[j - 1] == '*') {
                    if (j <= 1) {
                        // * 字符在首位的情况
                        continue;
                    }
                    // * 字符使前一字符重复 0 次
                    // a 与 a*，a 与 b* 的情况，前一字符匹配则匹配，否则不匹配
                    dp[i][j] = dp[i][j - 2];

                    if (!dp[i][j] && match(sarr, parr, i - 1, j - 2)) {
                        // 若 dp[i][j] 仍然为 false，那么继续尝试字符 * 使前一字符重复 1 次或多次的情况
                        // 首先 parr[j - 2] 必须等于 sarr[i - 1]，字符相同的情况下，重复才有意义
                        // aa 与 a* 的情况
                        dp[i][j] = dp[i - 1][j];
                    }
                } else {
                    // 字符匹配
                    if (match(sarr, parr, i - 1, j - 1)) {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                }
            }
        }
        return dp[slen][plen];
    }

    public static boolean match(char[] sarr, char[] parr, int i, int j) {
        if (i < 0) {
            return false;
        }
        if (parr[j] == '.') {
            return true;
        }
        return sarr[i] == parr[j];
    }
}
